// 查询p和q的最长公共border
#include "bits/stdc++.h"
using namespace std;

struct BorderTree {
  BorderTree() {}

  void add_edge(int u, int v) {
    g[u].push_back(v);
  }

  template<class T>
  void init(vector<T> s) {
    if (s.size() == 0) {
      return;
    }
    N = s.size();
    s.insert(s.begin(), s[0]);
    g.resize(N + 1);
    nex.resize(N + 1, 0);

    add_edge(0, 1);
    for (int i = 2, j = 0; i <= N; i++) {
      while (j && s[i] != s[j + 1]) {
        j = nex[j];
      }
      if (s[i] == s[j + 1]) {
        j++;
      }
      nex[i] = j;
      add_edge(j, i);
    }
    build();
  }

  void init(string s) {
    init<char>(vector<char>(s.begin(), s.end()));
  }

  void init(vector<int> s) {
    init<int>(s);
  }

  void dfs1(int u, int fa) {
    fat[u] = fa;
    dep[u] = dep[fa] + 1;
    siz[u] = 1;
    for (auto &v : g[u]) {
      if (v != fa) {
        dfs1(v, u);
        siz[u] += siz[v];
        if (son[u] == -1 || siz[son[u]] < siz[v]) {
          son[u] = v;
        }
      }
    }
  }

  void dfs2(int u, int tp) {
    top[u] = tp;
    if (son[u] != -1) {
      dfs2(son[u], tp);
    }
    for (auto &v : g[u]) {
      if (v != son[u] && v != fat[u]) {
        dfs2(v, v);
      }
    }
  }

  int get_len(int p, int q) {
    int fp = p, fq = q;
    while (top[p] != top[q]) {
      if (dep[top[p]] < dep[top[q]]) {
        swap(p, q);
      }
      p = fat[top[p]];
    }
    int ans = dep[p] < dep[q] ? p : q;
    if (ans == fp || ans == fq) {
      return fat[ans];
    }
    return p;
  }

  void build() {
    dep.resize(N + 1, 0);
    son.resize(N + 1, -1);
    siz.resize(N + 1, 0);
    fat.resize(N + 1, 0);
    top.resize(N + 1, 0);
    dfs1(0, -1);
    dfs2(0, 0);
  }

  int N;
  vector<int> nex, dep, son, siz, fat, top;
  vector<vector<int>> g;
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  string s;
  cin >> s;

  BorderTree bt;
  bt.init(s);

  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << bt.get_len(l, r) << '\n';
  }
  return 0;
}